package leetcode.code1420;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	int mod = (int) 1e9 + 7;

	public int numOfArrays(int n, int m, int k) {
		long[][][] dp = new long[k + 1][n + 1][m + 1];
		for (int j = 1; j <= m; j++) {
			dp[1][1][j] = 1;
		}
//		for (int i = 2; i <= n; i++) {
//			long sum = 0;
//			for (int j = 1; j <= m; j++) {
//				dp[K][i][j] = sum + dp[K][i - 1][j] * j;
//				sum += dp[K - 1][i - 1][j];
//				sum %= mod;
//				dp[K][i][j] %= mod;
//			}
//		}
//		H.print(dp[K]);
		for (int K = 1; K <= k; K++) {
			for (int i = 2; i <= n; i++) {
				long sum = 0;
				for (int j = 1; j <= m; j++) {
					dp[K][i][j] = sum + dp[K][i - 1][j] * j;
					sum += dp[K - 1][i - 1][j];
					sum %= mod;
					dp[K][i][j] %= mod;
				}
			}
		}
		long ans = 0;
		for (int i = 1; i <= m; i++) {
			ans += 1l * dp[k][n][i];
			ans %= mod;
		}
		return (int) ans;
	}

	@Override
	public void debug4() {
		H.compare(3, this.numOfArrays(2, 2, 1));
		H.compare(17, this.numOfArrays(5, 2, 1));
		H.compare(0, this.numOfArrays(5, 2, 3));
		H.compare(6, this.numOfArrays(2, 3, 1));
		H.compare(1, this.numOfArrays(9, 1, 1));
		H.compare(34549172, this.numOfArrays(50, 100, 25));
		H.compare(418930126, this.numOfArrays(37, 17, 7));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
